package com.sx.sx1.lintcode.day717;

import java.util.*;

public class LC900_LC1033_LC1195 {
    static class TreeNode {
        public int val;
        public TreeNode left, right;

        public TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }

    static class Solution {
        /**
         * @param root:   the given BST
         * @param target: the given target
         * @return: the value in the BST that is closest to the target
         */
        public int closestValue(TreeNode root, double target) {
            Queue<TreeNode> q = new LinkedList<>();
            q.add(root);
            int ans = root.val;
            double pre = Math.abs(root.val - target);

            while (!q.isEmpty()) {
                TreeNode pop = q.poll();
                double cur = Math.abs(pop.val - target);
                if (cur < pre) {
                    pre = cur;
                    ans = pop.val;
                }
                if (pop.left != null)
                    q.add(pop.left);

                if (pop.right != null) {
                    q.add(pop.right);
                }
            }

            return ans;
        }


    }

    public static void main(String[] args) {
        TreeNode t = new TreeNode(5);
        t.left = new TreeNode(4);
        t.right = new TreeNode(9);
        t.left.left = new TreeNode(2);
        t.right.left = new TreeNode(8);
        t.right.right = new TreeNode(10);
        System.out.println(new Solution().closestValue(t, 6.124780));
    }


    static class Solution1033 {
        /**
         * @param root: the root
         * @return: the minimum difference between the values of any two different nodes in the tree
         */
        public int minDiffInBST(TreeNode root) {
            Stack<TreeNode> stk = new Stack<>();
            TreeNode pre = null;
            int ans = 0;
            if (root.left != null) { //初始化保存结果的变量
                ans = Math.abs(root.val - root.left.val);
            }
            if (root.right != null) { //初始化保存结果的变量
                ans = Math.abs(root.val - root.right.val);
            }

            while (!stk.isEmpty() || root != null) {
                while (root != null) {
                    stk.add(root);
                    root = root.left;
                }

                root = stk.pop();
                if (pre != null) {
                    int cur = Math.abs(root.val - pre.val);
                    if (cur < ans) {
                        ans = cur;
                    }
                }

                pre = root;
                root = root.right;
            }
            return ans;
        }


    }




    static class Solution1195 {
        /**
         * @param root: a root of integer
         * @return: return a list of integer
         */
        public List<Integer> largestValues(TreeNode root) {
            List<Integer> ans =new ArrayList<>();
            Queue<TreeNode> q = new LinkedList<>();
            q.add(root);

            while (!q.isEmpty()){
                int size = q.size();
                int curmax = q.peek().val;
                for (int i = 0; i <size ; i++) {
                    TreeNode pop = q.poll();
                    if(pop.val> curmax){
                        curmax = pop.val;
                    }

                    if(pop.left!=null){
                        q.add(pop.left);
                    }

                    if(pop.right!=null){
                        q.add(pop.right);
                    }
                }

                ans.add(curmax);
            }
            return ans;
        }
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
900 · 二叉搜索树中最接近的值
算法
简单
通过率
54%

题目
题解95
笔记
讨论99+
排名
记录
描述
给一棵非空二叉搜索树以及一个target值，找到在BST中最接近给定值的节点值

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


给出的目标值为浮点数
我们可以保证只有唯一一个最接近给定值的节点
样例
样例1

输入: root = {5,4,9,2,#,8,10} and target = 6.124780
输出: 5
解释：
二叉树 {5,4,9,2,#,8,10}，表示如下的树结构：
        5
       / \
     4    9
    /    / \
   2    8  10
样例2

输入: root = {3,2,4,1} and target = 4.142857
输出: 4
解释：
二叉树 {3,2,4,1}，表示如下的树结构：
     3
    / \
  2    4
 /
1
标签
企业
Snapchat
Microsoft
Google
相关题目

901
二叉搜索树中最接近的值 II
困难
推荐课程

0基础入门数据分析
进阶大厂刚需高薪人才，熟练掌握SQL、Python、Tableau、A/Btest等实用技能工具，配套100+数据题夯实基础
65/133
已开启智能提示
发起考试
15 分 00 秒
12345678910111213141516171819202122
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }

控制台
历史提交

 */